package com.myc.subjects.string;

import java.util.ArrayList;
import java.util.List;

/**
 * LeetCode题号：43
 *
 * 字符串相乘
 *
 * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
 *
 * 示例 1:
 * 输入: num1 = "2", num2 = "3"
 * 输出: "6"
 *
 * 示例 2:=
 * 输入: num1 = "123", num2 = "456"
 * 输出: "56088"
 *
 * 说明：
 * num1 和 num2 的长度小于110。
 * num1 和 num2 只包含数字 0-9。
 * num1 和 num2 均不以零开头，除非是数字 0 本身。
 * 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/multiply-strings
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Zifuchuanxiangcheng {
    public static void main(String[] args) {
        String num1 = "78";
        String num2 = "234";
        Zifuchuanxiangcheng zifuchuanxiangcheng = new Zifuchuanxiangcheng();
        System.out.println(zifuchuanxiangcheng.multiply2(num1, num2));
    }

    /**
     * 方法一：模拟竖式计算
     * 时间复杂度：O(l1^2 + l1 * l2)   l1 = num1.length() l2 = num2.length
     * 模拟小学乘法竖式结构
     */

    public String multiply1(String num1, String num2) {
        //先处理特殊情况,如果有一个数为0，则结果为0，事先处理特殊情况会节省很多时间
        if("0".equals(num1) || "0".equals(num2)) return "0";

        int i = num1.length() - 1;//定义乘数的指针为i，从个位开始遍历
        String result = "0";//定义结果字符串

        //遍历乘数，与被乘数的每一位想乘
        while(i >= 0){
            int carry = 0;//进位
            int j = num2.length() - 1;//被乘数指针，从个位开始
            StringBuffer resultNum = new StringBuffer();//记录每个乘数的位与被乘数的乘积

            //先补0
            for(int k = 0; k < num1.length() - i - 1; k++){//第 i 位计算完成后要补上 num1.length() - i - 1 个 0
                resultNum.append('0');
            }

            //遍历被乘数
            while(j >= 0 || carry != 0){//carry如果有值还要在走一遍
                int n1 = num1.charAt(i) - '0';//i不会小于0，因为while条件 i >= 0
                int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;//j可能小于0，因为可能会有j < 0，同时carry不为0的情况
                int multi = n1 * n2 + carry;//乘积要加上carry进位
                resultNum.append(multi % 10);
                carry = multi / 10;
                j--;
            }

            resultNum.reverse();//需要将字符串反转
            result = addStrings(result,resultNum.toString());//结果字符串累加
            i--;
        }

        //处理多个0的问题,如果第一步就处理了特殊情况，那就不用再处理了
        //result = result.replaceFirst("^0*","");//将字符串前面所有的0清除
        //result = result.length() > 0 ? result : "0";//如果字符串被清空，就补个0

        return result;
    }

    /**
     * 方法二：方法一的改进：分布求和改为统一求和
     * 时间复杂度：O(l1 * l2)   l1 = num1.length() l2 = num2.length
     *
     * 数学推导1：
     * 位数为l1和l2的两个正整数的最大位数是多少？
     * 例 3位数与2位数想乘 最大是 999 * 99，我们知道 1000 * 100 = 100000 ，是个6位数。然而 999 * 99 的结果必然小于 100000,所以999 * 99的乘积最大是 3 + 2 = 5 位数
     * 结论：位数为l1和l2的两个正整数的最大位数为 l1 + l2
     *
     * 数学推导2：
     * 被乘数与乘数的乘积的个位应该累加到结果的第几位上？
     * 由方法一可知，当乘数的第i位，去乘以被乘数时，需要补上l1 - i - 1 个 0，那么这里乘数的第i位乘以被乘数的第j位时，需要补上的0的个数是 (l1 - i - 1) + (l2 - j -1),即 l1 + l2 - i - j - 2 个 0。
     * 那么从前往后的索引就应该是 ：结果的长度 - 结尾0的个数 - 1，那么则有 （l1 + l2） - (l1 + l2 - i - j - 2) - 1 = i + j + 1，他的前一位（需要累加进位）就是 i + j。
     * 结论：被乘数与乘数的乘积的个位应该累加到结果的第 i + j + 1 位上
     */
    public String multiply2(String num1, String num2) {
        if("0".equals(num1) || "0".equals(num2)) return "0";//处理特殊情况
        int l1 = num1.length();//l1为num1的位数
        int l2 = num2.length();//l2为num2的位数
        //定义结果数组
        int[] resultArray = new int[l1 + l2];//根据数学推算可知，l1位的数字与l2位的数字相乘最大位数为 l1 + l2 位
        int i = num1.length() - 1;//乘数指针
        while(i >= 0){
            int n1 = num1.charAt(i) - '0';//乘数的第i位的数字
            int j = num2.length() - 1;//被乘数指针
            while(j >= 0){
                int n2 = num2.charAt(j) - '0';//被乘数的第j位数字
                int multi = n1 * n2 + resultArray[i + j + 1];//将乘积与原位置（第 i + j + 1 位）上存储的值求和
                resultArray[i + j + 1] = multi % 10;//取出个位，放在该位置上
                resultArray[i + j] += multi / 10;//取出进位，加在进位的位置上
                j--;
            }
            i--;
        }
        //定义StringBuffer开始拼接结果字符串
        StringBuffer resultBuffer = new StringBuffer();
        int start = resultArray[0] == 0 ? 1 : 0;//判断第一位是不是0，如果是0，那就从第二位开始拼接
        for(int k = start; k < resultArray.length; k++){
            resultBuffer.append(resultArray[k]);
        }

        return resultBuffer.toString();
    }

    //字符串形式两数相加方法
    public String addStrings(String num1, String num2) {
        //定义结果StringBuffer
        StringBuffer result = new StringBuffer();

        //定义两个字符串上的指针，初始计算从个位开始，即字符串最后一位
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        //定义进位的值
        int carry = 0;
        while(i >= 0 || j >= 0 || carry != 0){
            int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;//这里小技巧使用charAt(index) - '0'的方式将字符串中的某个数转换成整形（ascii码相减）
            int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;//如果指针大于字符串的长度，则补0

            //将该数位的两数相加，注意加上进位
            int sum = n1 + n2 + carry;

            //将两数之和的个位保存进结果StringBuffer，十位保存进进位carry
            result.append(sum % 10);
            carry = sum / 10;

            i--;
            j--;
        }

        //循环结束要反转StringBuffer
        return result.reverse().toString();
    }

    //官方题解
    //做加法
    public String multiplyOfficial1(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        String ans = "0";
        int m = num1.length(), n = num2.length();
        for (int i = n - 1; i >= 0; i--) {
            StringBuffer curr = new StringBuffer();
            int add = 0;
            for (int j = n - 1; j > i; j--) {
                curr.append(0);
            }
            int y = num2.charAt(i) - '0';
            for (int j = m - 1; j >= 0; j--) {
                int x = num1.charAt(j) - '0';
                int product = x * y + add;
                curr.append(product % 10);
                add = product / 10;
            }
            if (add != 0) {
                curr.append(add % 10);
            }
            ans = addStrings(ans, curr.reverse().toString());
        }
        return ans;
    }

    public String addStringsOfficial(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        ans.reverse();
        return ans.toString();
    }

    //做乘法
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int m = num1.length(), n = num2.length();
        int[] ansArr = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            int x = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.charAt(j) - '0';
                ansArr[i + j + 1] += x * y;
            }
        }
        for (int i = m + n - 1; i > 0; i--) {
            ansArr[i - 1] += ansArr[i] / 10;
            ansArr[i] %= 10;
        }
        int index = ansArr[0] == 0 ? 1 : 0;
        StringBuffer ans = new StringBuffer();
        while (index < m + n) {
            ans.append(ansArr[index]);
            index++;
        }
        return ans.toString();
    }

}

/**
 * 总结：
 * 两数想乘可以使用分部求和，和统一求和两种方式，显然统一求和的时间复杂度更小
 * 这题的难点其实主要集中在方法二上的注释中的两个数学推导那里，掌握了之后就迎刃而解了
 */
